/**
 * 双指针
 * 61.旋转链表
 */
public class Exerciser2 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || k == 0) {
            return head;
        }
        ListNode newhaed = new ListNode(); // 哨兵位的头结点
        newhaed.next = head;
        // 1.找到最后一个节点，并记录，并且统计整个链表的长度
        int len = 0;
        ListNode tail = new ListNode();
        while(head != null) {
            tail = head;
            head = head.next;
            len++;
        }
        k %= len; // k可能很大，需要进行取余，当等于len的时候，就是不变的
        // 2.找到最后一个要移动的节点的前一个节点
        ListNode p = newhaed.next;
        for(int i = 1;i < len - k;i++) {
            p = p.next;
        }
        // 3.进行交换
        tail.next = newhaed.next;
        newhaed.next = p.next;
        p.next = null;
        return newhaed.next;
    }
}
